package codeRandomThoughts.Test134加油站;

import java.util.Arrays;

/**
 * 慢中之慢,超过5%
 */
public class Solution {
    public int canCompleteCircuit(int[] gas, int[] cost) {
        int len = gas.length;
        int sum = 0;
        int[] diff = new int[len];
        for (int i = 0; i < len; i++) {
            diff[i] = gas[i] - cost[i];
        }
        if (diff.length==1 && diff[0]>0) return 0;
        if (Arrays.stream(diff).sum() < 0) {
            return -1;
        }
        //首先找diff里面的正数,每找到一个,由它往后遍历n-1次,看过程中会不会出现负数
        //如果出现负数,代表无法到达
        for (int i = 0; i < diff.length; i++) {
            sum = 0;
            if (diff[i] > 0) {
                //从i所在的位置往后遍历n次
                for (int j = 0; j < len; j++) {
                    sum += diff[(i + j) % len];
                    if (sum < 0) {
                        break;
                    }
                }
                if (sum >= 0) {
                    return i;
                }
            }
        }
        return -1;
    }
}
